package com.cy.zcy;

import java.util.Stack;

/**
 * @Author: chenyun
 * @Date: 2021/09/23/15:27
 * @Description:
 */

//剑指 Offer II 027. 回文链表
//时间复杂度O(N)，额外空间复杂度O(1)
public class LinkDemo2 {

    //方法一：借助栈，如果是回文的话进栈后再出栈和原始的顺序相同
    public boolean isPalindrome1(ListNode head) {
        ListNode tem = head;
        Stack<ListNode> stack = new Stack<ListNode>();
        while (tem != null){
            stack.push(tem);
            tem = tem.next;
        }
        while (head != null){
            if(head.val == stack.pop().val){
                head = head.next;
            }else {
                return false;
            }
        }
        return true;
    }

    //方法二优化：时 O(n) 时间复杂度和 O(1) 空间复杂度
    public static boolean isPalindrome2(ListNode head) {
        ListNode mid1;   //链表的中间
        ListNode mid2;   //链表的中间
        ListNode end;   //链表的结尾
        ListNode low=head;
        ListNode fast=head;
        ListNode tem = null;
        if (head == null || head.next == null)
            return true;

        // 先快慢指针遍历一下链表,终止时fast指针根据链表长度奇偶
        // 表现为两种状态,fast == null或者fast.next == null
        while (fast != null && fast.next != null){
            low = low.next;  //慢指针走一步
            fast = fast.next.next;  //快指针走2步
        }
        //快指针走到结尾时候，慢指针来到中间
        end = fast;
        mid1 = low;
        tem = low;
        //右半段翻转
        while (tem != null){
            tem = mid1.next;
            tem.next = mid1;
            tem = tem.next;
        }
        while (head.val == end.val){
            head = head.next;
            end = end.next;
            if(head == mid1){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode A1 = new ListNode(1);
        ListNode A2 = new ListNode(2);
        ListNode A3 = new ListNode(2);
        ListNode A4 = new ListNode(1);
        A1.next = A2;
        A2.next = A3;
        A3.next = A4;
        A4.next = null;
        boolean flog = isPalindrome2(A1);
        System.out.println(flog);
    }


}
